# 输入两个单调递增的链表，输出两个链表合成后的链表，需要合成后的链表满足单调不减规则。
# 注意输入的两个链表都是单调递增的，所以这道题有巧妙的做法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 这个是方法1，最原始的做法
def get_merage_list(head1, head2):
    if head1 == None and head2 == None:
        return
    my_list = []
    while head1:
        my_list.append(head1.val)
        head1 = head1.next
    while head2:
        my_list.append(head2.val)
        head2 = head2.next
    my_list.sort()
    for i in range(len(my_list)):
        my_list[i] = ListNode(my_list[i])

    for i in range(len(my_list) - 1):
        my_list[i].next = my_list[i + 1]
    return my_list[0]


# 方法2,用了递归，非常巧妙，哪个更小，哪个就留下，剩下的再去比较
def Merage(pHead1, pHead2):
    if pHead1 == None:
        return pHead2
    if pHead2 == None:
        return pHead1

    if pHead1.val <= pHead2.val:
        pHead1.next = Merage(pHead1.next, pHead2)
        return pHead1
    else:
        pHead2.next = Merage(pHead2.next, pHead1)
        return pHead2
